/**
 * 148. 排序链表
 */
public class Solution_148 {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 定位链表中点
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        // 将链表分为两段
        slow.next = null;

        ListNode leftHead = sortList(head);
        ListNode rightHead = sortList(mid);
        return merge(leftHead, rightHead);
    }

    /**
     * 为 两个链表 进行 “归并排序”
     * 
     * @param leftHead  左链表头
     * @param rightHead 右链表头
     * @return 两个链表排序后的头节点
     */
    public ListNode merge(ListNode leftHead, ListNode rightHead) {
        if (leftHead == null) {
            return rightHead;
        }
        if (rightHead == null) {
            return leftHead;
        }
        if (leftHead.val <= rightHead.val) {
            leftHead.next = merge(leftHead.next, rightHead);
            return leftHead;
        } else {
            rightHead.next = merge(leftHead, rightHead.next);
            return rightHead;
        }
    }

    public static void main(String[] args) {
        Solution_148 solution = new Solution_148();
        ListNode head = new ListNode(4);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(3);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = null;
        System.out.print("排序前：");
        printListNode(head);
        ListNode ans = solution.sortList(head);
        System.out.print("排序后：");
        printListNode(ans);
    }

    /**
     * 输出链表
     */
    public static void printListNode(ListNode node) {
        System.out.print("[");
        while (node != null) {
            System.out.print(node.val + " -> ");
            node = node.next;
        }
        System.out.println("null]");
    }
}
